import tkinter as tk
import random
import numpy as np
from scipy.spatial import Delaunay
import heapq
import math


class DelaunayPathPlanner:
    def __init__(self, root, canvas_width=1000, canvas_height=1000):
        self.root = root
        self.canvas_width = canvas_width
        self.canvas_height = canvas_height
        self.midpoint_ratio = 1.0  # 默认中点比例
        self.num_rectangles = 5  # 默认小矩形数量
        self.if_four_point = 1  # 是否启用大矩形角点
        self.if_interact = 1  # 是否启用相交路径
        self.if_display = 1  # 是否启用显示

        # 创建框架，将按钮放置在右侧
        self.frame = tk.Frame(root)
        self.frame.pack(side=tk.RIGHT, fill=tk.Y)

        # 创建重置按钮
        self.reset_button = tk.Button(self.frame, text="重置", command=self.reset)
        self.reset_button.pack(pady=20)

        # 创建小矩形数量滑动条
        self.rectangle_slider = tk.Scale(self.frame, from_=1, to=10, orient=tk.HORIZONTAL, label="小矩形数量")
        self.rectangle_slider.set(self.num_rectangles)
        self.rectangle_slider.pack(pady=10)

        # 创建中点比例滑动条
        self.midpoint_slider = tk.Scale(self.frame, from_=0.1, to=1.0, resolution=0.1, orient=tk.HORIZONTAL,
                                        label="中点比例")
        self.midpoint_slider.set(self.midpoint_ratio)
        self.midpoint_slider.pack(pady=10)

        # 创建大矩形四个角点的滑动条
        self.if_four_point_slider = tk.Scale(self.frame, from_=0, to=1, orient=tk.HORIZONTAL, label="启用边框角点")
        self.if_four_point_slider.set(self.if_four_point)
        self.if_four_point_slider.pack(pady=10)

        # 创建调整检查路径相交的滑动条
        self.if_interact_slider = tk.Scale(self.frame, from_=0, to=1, orient=tk.HORIZONTAL, label="启用路径相交")
        self.if_interact_slider.set(self.if_interact)
        self.if_interact_slider.pack(pady=10)

        # 创建调整检查显示的滑动条
        self.if_display_slider = tk.Scale(self.frame, from_=0, to=1, orient=tk.HORIZONTAL, label="启用显示过程")
        self.if_display_slider.set(self.if_display)
        self.if_display_slider.pack(pady=10)

        # 创建画布
        self.canvas = tk.Canvas(root, width=canvas_width, height=canvas_height, bg="white")
        self.canvas.pack(side=tk.LEFT)

        self.reset()

    def reset(self):
        # 清空画布
        self.canvas.delete("all")

        # 更新参数
        self.num_rectangles = self.rectangle_slider.get()
        self.midpoint_ratio = self.midpoint_slider.get()
        self.if_four_point = self.if_four_point_slider.get()
        self.if_interact = self.if_interact_slider.get()
        self.if_display = self.if_display_slider.get()

        # 大矩形的范围
        self.rect_x1, self.rect_y1 = 100, 100  # 左上角
        self.rect_x2, self.rect_y2 = 900, 900  # 右下角
        self.large_rectangle = (self.rect_x1, self.rect_y1, self.rect_x2, self.rect_y2)
        self.canvas.create_rectangle(self.rect_x1, self.rect_y1, self.rect_x2, self.rect_y2, fill="lightblue")

        # 小矩形列表
        self.small_rectangles = self.generate_random_rectangles(int(self.num_rectangles), self.large_rectangle)

        # 绘制小矩形
        for rect in self.small_rectangles:
            self.canvas.create_rectangle(rect[0], rect[1], rect[2], rect[3], fill="lightgreen")

        # 获取所有小矩形的角点和其他随机点
        self.points = [(self.rect_x1, self.rect_y1, -1), (self.rect_x1, self.rect_y2, -1),
                       (self.rect_x2, self.rect_y1, -1), (self.rect_x2, self.rect_y2, -1)]
        for i, rect in enumerate(self.small_rectangles):
            self.points.extend(self.get_rectangle_corners_with_ids(rect, i))

        # 在矩形的边上生成额外的点
        if (self.if_four_point != 1):
            self.add_edge_points()

        # 执行Delaunay三角剖分，生成路径点集合和边集合
        self.path_points = self.delaunay_triangulation(self.points, self.small_rectangles, self.if_display)
        if (self.if_interact != 1):
            self.path_edges = self.get_path_edges(self.path_points, self.small_rectangles)
        else:
            self.path_edges = self.get_path_edges_check(self.path_points, self.small_rectangles)

        # 高亮显示并保存路径边
        self.highlight_and_save_edges(self.path_edges, self.if_display)

        # 绑定鼠标点击事件到画布
        self.canvas.bind("<Button-1>", self.on_canvas_click)

        # 路径规划状态
        self.click_count = 0
        self.start_point = None
        self.end_point = None
        self.nearest_start = None
        self.nearest_end = None

    def add_edge_points(self, step=50):
        """在大矩形的边上添加随机点"""
        edge_points = []

        # 上边
        for x in range(self.rect_x1, self.rect_x2 + 1, step):
            edge_points.append((x, self.rect_y1, -1))

        # 下边
        for x in range(self.rect_x1, self.rect_x2 + 1, step):
            edge_points.append((x, self.rect_y2, -1))

        # 左边
        for y in range(self.rect_y1, self.rect_y2 + 1, step):
            edge_points.append((self.rect_x1, y, -1))

        # 右边
        for y in range(self.rect_y1, self.rect_y2 + 1, step):
            edge_points.append((self.rect_x2, y, -1))

        # 随机打乱并添加到点集合中
        random.shuffle(edge_points)
        self.points.extend(edge_points)

    def is_overlapping(self, rect1, rect2):
        x11, y11, x12, y12 = rect1
        x21, y21, x22, y22 = rect2
        return not (x12 <= x21 or x22 <= x11 or y12 <= y21 or y22 <= y11)

    def is_too_close(self, rect1, rect2, min_spacing):
        x11, y11, x12, y12 = rect1
        x21, y21, x22, y22 = rect2

        # 计算水平和垂直方向上的最小距离
        horizontal_dist = max(0, max(x21 - x12, x11 - x22))
        vertical_dist = max(0, max(y21 - y12, y11 - y22))

        # 如果水平或垂直距离都小于最小间隔距离，则认为两个矩形太近
        return horizontal_dist < min_spacing and vertical_dist < min_spacing

    def generate_random_rectangles(self, num_rectangles, large_rect, min_margin=50, min_spacing=30):
        generated_rects = []
        for _ in range(num_rectangles):
            while True:
                width = random.randint(50, 200)
                height = random.randint(50, 200)
                # 留出与大矩形边界的最小距离
                x1 = random.randint(large_rect[0] + min_margin, large_rect[2] - width - min_margin)
                y1 = random.randint(large_rect[1] + min_margin, large_rect[3] - height - min_margin)
                x2 = x1 + width
                y2 = y1 + height
                new_rect = (x1, y1, x2, y2)

                # 检查与已有的小矩形之间是否有足够的距离
                if not any(
                        self.is_too_close(new_rect, existing_rect, min_spacing) for existing_rect in generated_rects):
                    generated_rects.append(new_rect)
                    break
        return generated_rects

    def get_rectangle_corners_with_ids(self, rect, rect_id):
        x1, y1, x2, y2 = rect
        return [(x1, y1, rect_id), (x1, y2, rect_id), (x2, y1, rect_id), (x2, y2, rect_id)]

    def line_intersects_rectangle(self, x1, y1, x2, y2, rect):
        rx1, ry1, rx2, ry2 = rect
        edges = [((rx1, ry1), (rx2, ry1)), ((rx1, ry2), (rx2, ry2)),
                 ((rx1, ry1), (rx1, ry2)), ((rx2, ry1), (rx2, ry2))]
        for (ex1, ey1), (ex2, ey2) in edges:
            if self.lines_intersect(x1, y1, x2, y2, ex1, ey1, ex2, ey2):
                return True
        return False

    def lines_intersect(self, x1, y1, x2, y2, x3, y3, x4, y4):
        def ccw(A, B, C):
            return (C[1] - A[1]) * (B[0] - A[0]) > (B[1] - A[1]) * (C[0] - A[0])

        return (ccw((x1, y1), (x3, y3), (x4, y4)) != ccw((x2, y2), (x3, y3), (x4, y4)) and
                ccw((x1, y1), (x2, y2), (x3, y3)) != ccw((x1, y1), (x2, y2), (x4, y4)))

    def delaunay_triangulation(self, points, small_rectangles, if_display):
        points_np = np.array([(x, y) for x, y, _ in points])
        tri = Delaunay(points_np)
        path_points = []

        for simplex in tri.simplices:
            for i in range(3):
                p1 = points[simplex[i]]
                p2 = points[simplex[(i + 1) % 3]]
                if p1[2] == p2[2]:
                    continue
                x1, y1 = p1[:2]
                x2, y2 = p2[:2]
                if if_display == 1:
                    self.canvas.create_line(x1, y1, x2, y2, fill="red")

                # 计算中点
                mid_x = (x1 + x2) / 2
                mid_y = (y1 + y2) / 2

                # 检查中点是否在小矩形内部或边界
                if not any(self.is_point_in_rectangle(mid_x, mid_y, rect) for rect in small_rectangles):
                    path_points.append((mid_x, mid_y))
                    r = 5
                    if if_display == 1:
                        self.canvas.create_oval(mid_x - r, mid_y - r, mid_x + r, mid_y + r, fill="yellow",
                                                outline="black")

        # 根据中点比例减少中点数量
        num_midpoints = max(1, int(len(path_points) * self.midpoint_ratio))
        return path_points[:num_midpoints]

    def is_point_in_rectangle(self, x, y, rect):
        x1, y1, x2, y2 = rect
        return x1 <= x <= x2 and y1 <= y <= y2

    def get_path_edges_check(self, path_points, small_rectangles):
        path_edges = []
        for i, (x1, y1) in enumerate(path_points):
            for j, (x2, y2) in enumerate(path_points):
                if i >= j:
                    continue
                if any(self.line_intersects_rectangle(x1, y1, x2, y2, rect) for rect in small_rectangles):
                    continue
                path_edges.append(((x1, y1), (x2, y2)))
        final_edges = []
        for edge in path_edges:
            if not any(self.lines_intersect(edge[0][0], edge[0][1], edge[1][0], edge[1][1],
                                            other_edge[0][0], other_edge[0][1], other_edge[1][0], other_edge[1][1])
                       for other_edge in final_edges if not self.has_same_endpoints(edge, other_edge)):
                final_edges.append(edge)
        return final_edges

    def get_path_edges(self, path_points, small_rectangles):
        path_edges = []
        for i, (x1, y1) in enumerate(path_points):
            for j, (x2, y2) in enumerate(path_points):
                if i >= j:
                    continue
                # 检查路径线是否与小矩形相交
                if any(self.line_intersects_rectangle(x1, y1, x2, y2, rect) for rect in small_rectangles):
                    continue
                path_edges.append(((x1, y1), (x2, y2)))

        # 不需要检查路径线之间是否相交，直接返回
        return path_edges

    def highlight_and_save_edges(self, edges, if_display, filename="path_edges.txt"):
        with open(filename, "w") as f:
            if (if_display == 1):
                for (x1, y1), (x2, y2) in edges:
                    self.canvas.create_line(x1, y1, x2, y2, fill="blue", width=2)
                    # f.write(f"({x1}, {y1}) -> ({x2}, {y2})\n")

    def has_same_endpoints(self, line1, line2):
        return (line1[0] == line2[0] and line1[1] == line2[1]) or (line1[0] == line2[1] and line1[1] == line2[0])

    def on_canvas_click(self, event):
        click_x, click_y = event.x, event.y
        if self.click_count == 0:
            if any(self.is_point_in_rectangle(click_x, click_y, rect) for rect in self.small_rectangles):
                return  # 如果点击在小矩形内部，则不处理

            self.start_point = (click_x, click_y)
            self.canvas.create_oval(self.start_point[0] - 5, self.start_point[1] - 5, self.start_point[0] + 5,
                                    self.start_point[1] + 5, fill="green")
            self.canvas.create_text(self.start_point[0], self.start_point[1] + 15, text="起点", fill="green",
                                    font=("Arial", 12, "bold"))
            self.nearest_start = self.find_nearest_point(self.start_point[0], self.start_point[1])
            if not self.line_intersects_rectangles(self.start_point[0], self.start_point[1], self.nearest_start[0],
                                                   self.nearest_start[1], self.small_rectangles):
                self.canvas.create_line(self.start_point[0], self.start_point[1], self.nearest_start[0],
                                        self.nearest_start[1], fill="green", width=2)
            self.click_count += 1
        elif self.click_count == 1:
            if any(self.is_point_in_rectangle(click_x, click_y, rect) for rect in self.small_rectangles):
                return  # 如果点击在小矩形内部，则不处理

            self.end_point = (click_x, click_y)
            self.canvas.create_oval(self.end_point[0] - 5, self.end_point[1] - 5, self.end_point[0] + 5,
                                    self.end_point[1] + 5, fill="red")
            self.canvas.create_text(self.end_point[0], self.end_point[1] + 15, text="终点", fill="red",
                                    font=("Arial", 12, "bold"))
            self.nearest_end = self.find_nearest_point(self.end_point[0], self.end_point[1])
            if not self.line_intersects_rectangles(self.end_point[0], self.end_point[1], self.nearest_end[0],
                                                   self.nearest_end[1], self.small_rectangles):
                self.canvas.create_line(self.end_point[0], self.end_point[1], self.nearest_end[0],
                                        self.nearest_end[1], fill="red", width=2)
            self.click_count = 0

            # Dijkstra算法查找最短路径
            self.find_shortest_path()

    def line_intersects_rectangles(self, x1, y1, x2, y2, small_rectangles):
        return any(self.line_intersects_rectangle(x1, y1, x2, y2, rect) for rect in small_rectangles)

    def find_nearest_point(self, x, y):
        min_dist = float("inf")
        nearest_point = None
        for point in self.path_points:
            dist = math.hypot(x - point[0], y - point[1])
            if dist < min_dist:
                min_dist = dist
                nearest_point = point
        return nearest_point

    def find_shortest_path(self):
        graph = {}
        for (x1, y1), (x2, y2) in self.path_edges:
            if (x1, y1) not in graph:
                graph[(x1, y1)] = []
            if (x2, y2) not in graph:
                graph[(x2, y2)] = []
            dist = math.hypot(x2 - x1, y2 - y1)
            graph[(x1, y1)].append(((x2, y2), dist))
            graph[(x2, y2)].append(((x1, y1), dist))

        # 使用优先队列和Dijkstra算法
        pq = [(0, self.nearest_start)]
        dist_map = {self.nearest_start: 0}
        prev_map = {self.nearest_start: None}
        while pq:
            current_dist, current_point = heapq.heappop(pq)
            if current_point == self.nearest_end:
                break
            for neighbor, distance in graph.get(current_point, []):
                new_dist = current_dist + distance
                if neighbor not in dist_map or new_dist < dist_map[neighbor]:
                    dist_map[neighbor] = new_dist
                    prev_map[neighbor] = current_point
                    heapq.heappush(pq, (new_dist, neighbor))

        # 重建最短路径
        path = []
        current_point = self.nearest_end
        while current_point is not None:
            path.append(current_point)
            current_point = prev_map.get(current_point)
        path = path[::-1]

        # 在画布上绘制最短路径
        for i in range(len(path) - 1):
            self.canvas.create_line(path[i][0], path[i][1], path[i + 1][0], path[i + 1][1], fill="yellow", width=3)


def main():
    root = tk.Tk()
    root.title("Delaunay Path Planner")
    planner = DelaunayPathPlanner(root)
    root.mainloop()


if __name__ == "__main__":
    main()
